{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #行星碰撞"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: asteroidCollision"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #行星碰撞"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>asteroids</code>，表示在同一行的小行星。</p>\n",
    "\n",
    "<p>对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。</p>\n",
    "\n",
    "<p>找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>asteroids = [5,10,-5]\n",
    "<strong>输出：</strong>[5,10]\n",
    "<b>解释：</b>10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>asteroids = [8,-8]\n",
    "<strong>输出：</strong>[]\n",
    "<b>解释：</b>8 和 -8 碰撞后，两者都发生爆炸。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>asteroids = [10,2,-5]\n",
    "<strong>输出：</strong>[10]\n",
    "<b>解释：</b>2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>asteroids = [-2,-1,1,2]\n",
    "<strong>输出：</strong>[-2,-1,1,2]\n",
    "<b>解释</b><strong>：</strong>-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。 </pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= asteroids.length&nbsp;&lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000 &lt;= asteroids[i] &lt;= 1000</code></li>\n",
    "\t<li><code>asteroids[i] != 0</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 735&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/asteroid-collision/\">https://leetcode-cn.com/problems/asteroid-collision/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [XagZNi](https://leetcode.cn/problems/XagZNi/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [XagZNi](https://leetcode.cn/problems/XagZNi/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,10,-5]', '[8,-8]', '[10,2,-5]', '[-2,-1,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        n = len(asteroids)-1\n",
    "        while asteroids:\n",
    "            if n == left:\n",
    "                break\n",
    "            elif asteroids[left]<0:\n",
    "                left += 1\n",
    "            elif n == left:\n",
    "                break\n",
    "            elif asteroids[left+1]<0 and asteroids[left]+asteroids[left+1]>0:\n",
    "                asteroids.pop(left+1)\n",
    "                n -= 1\n",
    "            elif n == left:\n",
    "                break\n",
    "            elif asteroids[left+1]<0 and asteroids[left]+asteroids[left+1]==0:\n",
    "                asteroids.pop(left+1)\n",
    "                asteroids.pop(left)\n",
    "                if left!=0:\n",
    "                    left -= 1\n",
    "                n -= 2\n",
    "            elif n == left:\n",
    "                break\n",
    "            elif asteroids[left+1]<0 and asteroids[left]+asteroids[left+1]<0:\n",
    "                asteroids.pop(left)\n",
    "                if left!=0:\n",
    "                    left -= 1\n",
    "                n -= 1\n",
    "            elif n == left:\n",
    "                break\n",
    "            #asteroids[left+1]>0\n",
    "            else:\n",
    "                left += 1\n",
    "        return asteroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        n=len(asteroids)\n",
    "        \n",
    "        l=0\n",
    "        \n",
    "        \n",
    "        while l<n:\n",
    "            l=0\n",
    "            while l<n  and asteroids[l]<0:l+=1\n",
    "            if l==n: break\n",
    "            r=l\n",
    "            while  r<n and asteroids[r]>0: r+=1\n",
    "            if r==n:break\n",
    "            if abs(asteroids[r])>abs(asteroids[r-1]):\n",
    "                asteroids.pop(r-1)\n",
    "                n-=1\n",
    "                r-=1\n",
    "            elif abs(asteroids[r])==abs(asteroids[r-1]):\n",
    "                asteroids.pop(r)\n",
    "                asteroids.pop(r-1)\n",
    "                n-=2\n",
    "                r-=2\n",
    "\n",
    "            else:\n",
    "                asteroids.pop(r)\n",
    "                n-=1\n",
    "                r-=1\n",
    "\n",
    "        return asteroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        #0053\n",
    "        l=len(asteroids)\n",
    "        i=1\n",
    "        while(i<l):\n",
    "            if asteroids[i]<0 and i>0 and asteroids[i-1]>0:\n",
    "                if -asteroids[i]==asteroids[i-1]:\n",
    "                    asteroids.pop(i)\n",
    "                    asteroids.pop(i-1)\n",
    "                    l-=2\n",
    "                    i=i-2\n",
    "                elif -asteroids[i]>asteroids[i-1]:\n",
    "                    asteroids.pop(i-1)\n",
    "                    l-=1\n",
    "                    i=i-2\n",
    "                elif -asteroids[i]<asteroids[i-1]:\n",
    "                    asteroids.pop(i)\n",
    "                    l-=1\n",
    "                    i=i-1\n",
    "            i+=1\n",
    "        print(asteroids)\n",
    "        return asteroids\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        s = len(asteroids) + 1\n",
    "        t = len(asteroids)\n",
    "        while s > t:\n",
    "            s = t\n",
    "            for i in range(len(asteroids)-2, -1, -1):\n",
    "                if asteroids[i + 1] < 0 and asteroids[i] > 0:\n",
    "                    if abs(asteroids[i + 1]) > asteroids[i]:\n",
    "                        asteroids.pop(i)\n",
    "                    elif abs(asteroids[i + 1]) < asteroids[i]:\n",
    "                        asteroids.pop(i + 1)\n",
    "                    else:\n",
    "                        asteroids.pop(i + 1)\n",
    "                        asteroids.pop(i)\n",
    "                    if len(asteroids)-2 < i:\n",
    "                        break\n",
    "            t = len(asteroids)\n",
    "        return asteroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, a: List[int]) -> List[int]:\n",
    "        \n",
    "        i=0\n",
    "        n=len(a)\n",
    "        while i<n-1:\n",
    "            if a[i]>0 and a[i+1]<0:\n",
    "                if a[i]>-a[i+1]:\n",
    "                    a=a[:i+1]+a[i+2:]\n",
    "                    n-=1\n",
    "                elif a[i]<-a[i+1]:\n",
    "                    a=a[:i]+a[i+1:]\n",
    "                    n-=1\n",
    "                else:\n",
    "                    a=a[:i]+a[i+2:]\n",
    "                    n-=2\n",
    "                if i-1 >=0:\n",
    "                    i-=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return a[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        for x in asteroids:\n",
    "            while s and x < 0 < s[-1]:\n",
    "                if s[-1] < -x:\n",
    "                    s.pop()\n",
    "                    continue\n",
    "                elif s[-1] == -x:\n",
    "                    s.pop()\n",
    "                break\n",
    "            else:\n",
    "                s.append(x)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def asteroidCollision(self, asteroids):\n",
    "#         s, p = [], 0\n",
    "#         while p < len(asteroids):\n",
    "#             if not s or s[-1] < 0 or asteroids[p] > 0:\n",
    "#                 s.append(asteroids[p])\n",
    "#             elif s[-1] <= -asteroids[p]:\n",
    "#                 if s.pop() < -asteroids[p]:\n",
    "#                     continue\n",
    "#             p += 1\n",
    "#         return s\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        s,p=[],0\n",
    "        while p<len(asteroids):\n",
    "            if not s or s[-1]<0 or asteroids[p]>0:\n",
    "                s.append(asteroids[p])\n",
    "\n",
    "            elif s[-1]<=-asteroids[p]:\n",
    "                if s.pop()<-asteroids[p]:\n",
    "                    continue\n",
    "            p+=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for i in asteroids:\n",
    "            flag = True\n",
    "            while stack and flag:\n",
    "                if i < 0 and stack[-1]>0:\n",
    "                    if abs(i)<abs(stack[-1]):flag = False\n",
    "                    elif abs(i)==abs(stack[-1]):\n",
    "                        stack.pop()\n",
    "                        flag = False\n",
    "                    else:stack.pop()\n",
    "                else:break\n",
    "            if flag:stack.append(i)\n",
    "        return stack     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for i in range(len(asteroids)):\n",
    "            isexsit = True\n",
    "            while isexsit and asteroids[i]<0 and stack and stack[-1]>0:\n",
    "                if stack[-1] >= -asteroids[i]:\n",
    "                    isexsit = False\n",
    "                if stack[-1] <= -asteroids[i]:\n",
    "                    stack.pop()\n",
    "            if isexsit:\n",
    "                stack.append(asteroids[i])\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        n = len(asteroids)-1\n",
    "        while asteroids:\n",
    "            if n == left:\n",
    "                break\n",
    "            elif asteroids[left]<0:\n",
    "                left += 1\n",
    "            elif n == left:\n",
    "                break\n",
    "            elif asteroids[left+1]<0 and asteroids[left]+asteroids[left+1]>0:\n",
    "                asteroids.pop(left+1)\n",
    "                n -= 1\n",
    "            elif n == left:\n",
    "                break\n",
    "            elif asteroids[left+1]<0 and asteroids[left]+asteroids[left+1]==0:\n",
    "                asteroids.pop(left+1)\n",
    "                asteroids.pop(left)\n",
    "                if left!=0:\n",
    "                    left -= 1\n",
    "                n -= 2\n",
    "            elif n == left:\n",
    "                break\n",
    "            elif asteroids[left+1]<0 and asteroids[left]+asteroids[left+1]<0:\n",
    "                asteroids.pop(left)\n",
    "                if left!=0:\n",
    "                    left -= 1\n",
    "                n -= 1\n",
    "            elif n == left:\n",
    "                break\n",
    "                #asteroids[left+1]>0\n",
    "            else:\n",
    "                left += 1\n",
    "        return asteroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, a: List[int]) -> List[int]:\n",
    "        \n",
    "        i=0\n",
    "        while i<len(a)-1:\n",
    "            if a[i]>0 and a[i+1]<0 :\n",
    "                if a[i]<-a[i+1]:\n",
    "                    a=a[:i]+a[i+1:]\n",
    "                    if i-1 >=0:\n",
    "                        i-=1\n",
    "                elif a[i]>-a[i+1]:\n",
    "                    a=a[:i+1]+a[i+2:]\n",
    "                else:\n",
    "                    a=a[:i]+a[i+2:]\n",
    "                    if i-1 >=0:\n",
    "                        i-=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack=[]\n",
    "        for i in asteroids:\n",
    "            alive=True\n",
    "            while alive and i<0 and stack and stack[-1]>0:\n",
    "                alive = stack[-1] < -i\n",
    "                if stack[-1] <= -i:\n",
    "                    stack.pop()\n",
    "            if alive:\n",
    "                stack.append(i)\n",
    "\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for aster in asteroids:\n",
    "            alive = True\n",
    "            while alive and aster < 0 and st and st[-1] > 0:\n",
    "                alive = st[-1] < -aster\n",
    "                if st[-1] <= -aster:\n",
    "                    st.pop()\n",
    "            if alive:\n",
    "                st.append(aster)\n",
    "        return st\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        s=[]\n",
    "        for x in asteroids:\n",
    "            if x>0:\n",
    "                s.append(x)\n",
    "            else:\n",
    "                while s and s[-1]>0 and s[-1]<-x:\n",
    "                    s.pop()\n",
    "                if s and s[-1]==-x:\n",
    "                    s.pop()\n",
    "                elif not s or s[-1]<0:\n",
    "                    s.append(x)\n",
    "        return s\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for aster in asteroids:\n",
    "            alive = True\n",
    "            while alive and aster < 0 and st and st[-1] > 0:\n",
    "                alive = st[-1] < -aster\n",
    "                if st[-1] <= -aster:\n",
    "                    st.pop()\n",
    "            if alive:\n",
    "                st.append(aster)\n",
    "        return st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        def solution(asteroids):\n",
    "            for i in range(len(asteroids) - 1):\n",
    "                if asteroids[i] > 0 and asteroids[i + 1] < 0:\n",
    "                    return [True, i , i + 1]\n",
    "            return [False, 0, 0]\n",
    "        while True:\n",
    "            if solution(asteroids)[0]:\n",
    "                i = solution(asteroids)[1]\n",
    "                j = solution(asteroids)[2]\n",
    "                if abs(asteroids[i]) == abs(asteroids[j]):\n",
    "                    del_idx = [i, j]\n",
    "                    asteroids = [num for i, num in enumerate(asteroids) if i not in del_idx]\n",
    "                elif abs(asteroids[i]) > abs(asteroids[j]):\n",
    "                    asteroids.pop(j)\n",
    "                else:\n",
    "                    asteroids.pop(i)\n",
    "            else:\n",
    "                break\n",
    "        return asteroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        # 在相撞完成后，列表左边一定全是向左的，右边一定全是向右的\n",
    "        stack = []\n",
    "        for astetoid in asteroids:\n",
    "            # 向左飞行的一直碰撞\n",
    "            # print(stack)\n",
    "            while len(stack)>0 and astetoid<0 and stack[-1]>0 and astetoid<-stack[-1]:\n",
    "                stack.pop()\n",
    "\n",
    "            if len(stack)>0 and astetoid<0 and astetoid==-stack[-1]:\n",
    "                stack.pop()\n",
    "            elif len(stack)>0 and astetoid<0 and astetoid>-stack[-1]:\n",
    "                continue\n",
    "            else:\n",
    "                stack.append(astetoid)\n",
    "        return (stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack: List[int] = []\n",
    "        for asteroid in asteroids:\n",
    "            alive = True\n",
    "            while alive and asteroid < 0 and stack and stack[-1] > 0:\n",
    "                alive = stack[-1] < -asteroid\n",
    "                if stack[-1] <= -asteroid:\n",
    "                    stack.pop()\n",
    "            if alive:\n",
    "                stack.append(asteroid)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        # stack = []\n",
    "        # for a in asteroids:\n",
    "        #     alive = True\n",
    "        #     while alive and a <0 and stack and stack[-1]>0:\n",
    "        #         alive = stack[-1] <-a\n",
    "        #         if stack[-1] <= -a: stack.pop()\n",
    "        #     if alive:\n",
    "        #         stack.append(a)\n",
    "        # return stack\n",
    "        stack = []\n",
    "        for a in asteroids:\n",
    "            flag = True\n",
    "            while flag and a<0 and stack and stack[-1]>0:\n",
    "                flag = stack[-1] < -a\n",
    "                if stack[-1] <= -a: stack.pop()\n",
    "            if flag:\n",
    "                stack.append(a)\n",
    "        return stack\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        g = []\n",
    "        for a in asteroids:\n",
    "            while g and g[-1] > 0 and a < 0:\n",
    "                b = g.pop()\n",
    "                a = a if a + b < 0 else (b if a + b > 0 else 0)\n",
    "            if a:\n",
    "                g.append(a)\n",
    "        return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        store = []\n",
    "        for ast in asteroids:\n",
    "            # print(store)\n",
    "            if len(store) == 0:\n",
    "                store.append(ast)\n",
    "            else:\n",
    "                near_ast = store[-1]\n",
    "                # print(near_ast)\n",
    "                # print(ast)\n",
    "                if near_ast*ast > 0:\n",
    "                    store.append(ast)\n",
    "                    continue\n",
    "                if near_ast < 0 and ast > 0:\n",
    "                    store.append(ast)\n",
    "                    continue\n",
    "                while near_ast > 0 and ast < 0:\n",
    "                    # print(near_ast)\n",
    "                    # print(ast)\n",
    "                    store.pop()\n",
    "                    if abs(near_ast) > abs(ast):\n",
    "                        ast = near_ast\n",
    "                        \n",
    "                    elif abs(near_ast) == abs(ast):\n",
    "                        ast = 0\n",
    "                    if len(store) == 0:\n",
    "                        break\n",
    "                    near_ast = store[-1]\n",
    "                if ast != 0:\n",
    "                    store.append(ast)\n",
    "                    \n",
    "        return store\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stk = []\n",
    "        for x in asteroids:\n",
    "            while stk and stk[-1] > 0 and x < 0 and stk[-1] < -x:\n",
    "                stk.pop()\n",
    "            if stk and stk[-1] > 0 and x < 0 and stk[-1] >= -x:\n",
    "                if stk[-1] == -x: stk.pop()\n",
    "            else:\n",
    "                stk.append(x)\n",
    "        return stk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        ans, p = [], 0\n",
    "        while p < len(asteroids):\n",
    "            if not ans or ans[-1] < 0 or asteroids[p] > 0:\n",
    "                ans.append(asteroids[p])\n",
    "            elif ans[-1] <= -asteroids[p]:\n",
    "                if ans.pop() < -asteroids[p]:\n",
    "                    continue\n",
    "            p += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for cur_ast in asteroids:\n",
    "            while stack and stack[-1] > 0 and cur_ast < 0:\n",
    "                pre_ast = stack.pop()\n",
    "                if abs(pre_ast) > abs(cur_ast):\n",
    "                    stack.append(pre_ast)\n",
    "                    cur_ast = 0\n",
    "                    break\n",
    "                elif abs(pre_ast) == abs(cur_ast):\n",
    "                    cur_ast = 0\n",
    "                    break\n",
    "            if cur_ast:\n",
    "                stack.append(cur_ast)\n",
    "        return stack\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    只有排在前面的正数和排在后面的负数才能碰撞\n",
    "    1. 遇到正数时，加到结果里面，等待碰撞\n",
    "    2. 遇到负数x时，向左寻找，遇到y，如果y<0，则停止，如果y>0，会碰撞：\n",
    "            |x| < y: x消失，停止\n",
    "            |x| = y: x和y一起消失，停止\n",
    "            |x| > y: y消失，x继续向左寻找\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for x in asteroids:\n",
    "            if x > 0:\n",
    "                stack.append(x)\n",
    "            else:\n",
    "                while stack and stack[-1] > 0 and stack[-1] < -x:\n",
    "                    stack.pop()\n",
    "                if stack and stack[-1] == -x:\n",
    "                    stack.pop()\n",
    "                    continue\n",
    "                if not stack or stack[-1] < 0:\n",
    "                    stack.append(x)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        stack = []\n",
    "        for star in asteroids:\n",
    "            if star > 0 :\n",
    "                stack.append(star)\n",
    "            elif star < 0:\n",
    "                while stack:\n",
    "                    x = stack.pop()\n",
    "                    if x > - star:\n",
    "                        stack.append(x)\n",
    "                        break\n",
    "                    elif x == - star:\n",
    "                        star = 0\n",
    "                        break\n",
    "                if not stack and star:\n",
    "                    ans.append(star)\n",
    "        \n",
    "        return ans + stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for x in asteroids:\n",
    "            if not stack or x>0:\n",
    "                stack.append(x)\n",
    "            else: #x<0\n",
    "                while 1:\n",
    "                    top = stack[-1] if stack else None\n",
    "                    if top is None:\n",
    "                        stack.append(x)\n",
    "                        break \n",
    "                    elif top < 0:\n",
    "                        stack.append(x)\n",
    "                        break\n",
    "                    elif abs(top) > abs(x):\n",
    "                        break\n",
    "                    elif abs(top) == abs(x):\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                    elif abs(top) < abs(x):\n",
    "                        stack.pop()\n",
    "                        continue\n",
    "                    else:\n",
    "                        break\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for i in asteroids:\n",
    "            add = True\n",
    "            if i < 0:\n",
    "                while stack and stack[-1] > 0 and stack[-1]<-i:\n",
    "                    stack.pop()\n",
    "                if stack and stack[-1]>0:\n",
    "                    add = False\n",
    "                    if stack and stack[-1] == -i:\n",
    "                        stack.pop()\n",
    "            if add:\n",
    "                stack.append(i)\n",
    "        return stack\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        # 只有左栈和右栈同时不为空时才会发生相撞\n",
    "        left_stack = []\n",
    "        right_stack = []\n",
    "        # no_use表示左侧的行星往左跑, 永远不会撞到其他行星\n",
    "        no_use = []\n",
    "        for i in asteroids:\n",
    "            if i < 0:\n",
    "                if len(left_stack) > 0:\n",
    "                    right_stack.append(i)\n",
    "                else:\n",
    "                    no_use.append(i)\n",
    "            elif i > 0:\n",
    "                left_stack.append(i)\n",
    "            while left_stack and right_stack:\n",
    "                num1 = left_stack.pop()\n",
    "                num2 = right_stack.pop(0)\n",
    "                if abs(num1) > abs(num2):\n",
    "                    left_stack.append(num1)\n",
    "                elif abs(num1) < abs(num2):\n",
    "                    if len(left_stack) > 0:\n",
    "                        right_stack.append(num2)\n",
    "                    else:\n",
    "                        no_use.append(num2)\n",
    "        return no_use + left_stack + right_stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        s, p = [], 0\n",
    "        while p < len(asteroids):\n",
    "            if not s or s[-1] < 0 or asteroids[p] > 0:\n",
    "                s.append(asteroids[p])\n",
    "            elif s[-1] <= -asteroids[p]:\n",
    "                if s.pop() < -asteroids[p]:\n",
    "                    continue\n",
    "            p += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(asteroids)\n",
    "        flag = [False] * n\n",
    "        for i in range(n):\n",
    "            while stack and asteroids[stack[-1]] > 0 and asteroids[i] < 0:\n",
    "                if abs(asteroids[stack[-1]]) > abs(asteroids[i]):\n",
    "                    flag[i] = True\n",
    "                    break\n",
    "                elif abs(asteroids[stack[-1]]) < abs(asteroids[i]):\n",
    "                    flag[stack.pop()] = True\n",
    "                else:\n",
    "                    flag[i] = True\n",
    "                    flag[stack.pop()] = True\n",
    "                    break\n",
    "            if flag[i]:\n",
    "                continue\n",
    "            stack.append(i)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if flag[i]:\n",
    "                continue\n",
    "            ans.append(asteroids[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for a in asteroids:\n",
    "            while stack and 0 < stack[-1] < a * -1:     # 只有栈顶炸\n",
    "                stack.pop()\n",
    "            if not stack or stack[-1] < 0 or a > 0:     # 不发生爆炸\n",
    "                stack.append(a)\n",
    "            elif a * -1 == stack[-1]:                   # 同时爆炸\n",
    "                stack.pop()\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack, p = [], 0\n",
    "        while p < len(asteroids):\n",
    "            if stack==[] or stack[-1]<0 or asteroids[p]>0:\n",
    "                stack.append(asteroids[p])\n",
    "            elif stack[-1] <= -asteroids[p]:\n",
    "                if stack.pop() < -asteroids[p]:\n",
    "                    continue\n",
    "            p = p + 1\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, a: List[int]) -> List[int]:\n",
    "        \n",
    "        i=0\n",
    "        top=-1;st=[0]*len(a)\n",
    "        while i<len(a):\n",
    "            flag=True\n",
    "            while flag and top!=-1 and st[top]>0 and a[i]<0 :\n",
    "                if st[top]>=-a[i]:\n",
    "                    flag=False\n",
    "                if st[top]<=-a[i]:\n",
    "                    top-=1\n",
    "            if flag:\n",
    "                top+=1\n",
    "                st[top]=a[i]\n",
    "            i+=1\n",
    "        return st[:top+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        stack = []\n",
    "        for item in asteroids:\n",
    "            flag = True\n",
    "            while item < 0 and stack and stack[-1] > 0 and flag:\n",
    "                flag = abs(item) > abs(stack[-1])\n",
    "                if abs(item) > abs(stack[-1]):\n",
    "                    stack.pop()\n",
    "                elif abs(item) < abs(stack[-1]):\n",
    "                    pass\n",
    "                else:\n",
    "                    stack.pop()\n",
    "            if flag:\n",
    "                stack.append(item)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, a):\n",
    "        stack = []\n",
    "        i = 0\n",
    "\n",
    "        while i < len(a):\n",
    "            # 如果行星为 +\n",
    "            if a[i] > 0:\n",
    "                stack.append(a[i])\n",
    "            # 如果行星为 -\n",
    "            else:\n",
    "                if stack:\n",
    "                    if stack[-1] > 0:  # 如果有 +\n",
    "                        while stack and 0 < stack[-1] < -a[i]:\n",
    "                            stack.pop()\n",
    "                        if stack:\n",
    "                            if stack[-1] == -a[i]:\n",
    "                                stack.pop()\n",
    "                            elif stack[-1] < 0:\n",
    "                                stack.append(a[i])\n",
    "                        else:\n",
    "                            stack.append(a[i])\n",
    "                    elif stack[-1] < 0:\n",
    "                        stack.append(a[i])\n",
    "                else:\n",
    "                    stack.append(a[i])\n",
    "            i += 1\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for asteroid in asteroids:\n",
    "            if not ans:\n",
    "                ans.append(asteroid)\n",
    "                continue\n",
    "            if asteroid > 0:\n",
    "                ans.append(asteroid)\n",
    "            else:\n",
    "                if ans[-1] < 0:\n",
    "                    ans.append(asteroid)\n",
    "                else:\n",
    "                    while ans:\n",
    "                        if asteroid > 0 and ans[-1] > 0:\n",
    "                            break\n",
    "                        if asteroid < 0 and ans[-1] < 0:\n",
    "                            break\n",
    "                        if abs(asteroid) == ans[-1]:\n",
    "                            asteroid = 0\n",
    "                            ans.pop()\n",
    "                            break\n",
    "                        if abs(asteroid) < ans[-1]:\n",
    "                            asteroid = 0\n",
    "                            break\n",
    "                        ans.pop()\n",
    "                    if abs(asteroid):\n",
    "                        ans.append(asteroid)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, nums: List[int]) -> List[int]:\n",
    "        stk = []\n",
    "        for x in nums:\n",
    "            if x < 0:\n",
    "                while stk and stk[-1] > 0:\n",
    "                    if stk[-1] + x > 0:\n",
    "                        x = 0\n",
    "                        break\n",
    "                    elif stk[-1] + x == 0:\n",
    "                        x = 0\n",
    "                        stk.pop()\n",
    "                        break\n",
    "                    else:\n",
    "                        stk.pop()\n",
    "            if x != 0:\n",
    "                stk.append(x)\n",
    "        return stk\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        #0053\n",
    "        l=len(asteroids)\n",
    "        st=[]\n",
    "        for i in range(l):\n",
    "            if asteroids[i]>0:\n",
    "                st.append(asteroids[i])\n",
    "            else:\n",
    "                if st==[] or st[-1]<0:\n",
    "                    st.append(asteroids[i])\n",
    "                while(-asteroids[i]>=st[-1] and st[-1]>0):\n",
    "                    if -asteroids[i]==st[-1]:\n",
    "                        st.pop()\n",
    "                        break\n",
    "                    st.pop()\n",
    "                    if st==[] or st[-1]<0:\n",
    "                        st.append(asteroids[i])\n",
    "                        break\n",
    "        return st\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        # 行星列表小于等于1，直接返回\n",
    "        if len(asteroids)<=1:\n",
    "            return asteroids\n",
    "        \n",
    "        # 分治+递归\n",
    "        def mergecollision(seq):\n",
    "            if len(seq) <= 1:\n",
    "                return seq\n",
    "            mid = len(seq) // 2 \n",
    "            left = mergecollision(seq[:mid])\n",
    "            # print(\"left\",left)\n",
    "            right = mergecollision(seq[mid:])\n",
    "            # print(\"right\",right)\n",
    "            return merge(left, right)\n",
    "\n",
    "        # 合并\n",
    "        def merge(left, right):\n",
    "            # print(\"进入合并前的left,right\",left,right)\n",
    "            # 如果两个列表有一个为空，直接合并返回\n",
    "            if (len(left)==0)|(len(right)==0):\n",
    "                return left+right\n",
    "            # 碰撞过程，从中间开始碰撞。 两边的都是碰撞过的不会内部碰撞\n",
    "            i = len(left)-1  # \n",
    "            j = 0\n",
    "            while i >=0  and j < len(right):\n",
    "                if (left[i] < 0) & (right[j]>0):  # 移动方向相反不碰撞\n",
    "                    break\n",
    "                elif ((left[i]>0)&(right[j]>0))|((left[i]<0)&(right[j]<0)): # 方向相同不碰撞\n",
    "                    break\n",
    "                elif left[i] < -right[j]: # 左边绝对值小\n",
    "                    i -= 1\n",
    "                elif left[i] > -right[j]:  # 左边绝对值大\n",
    "                    j += 1\n",
    "                else:  # 两边相等，一起爆炸\n",
    "                    i -= 1\n",
    "                    j += 1\n",
    "            # print(\"合并结果\",left[:i+1]+right[j:])\n",
    "            return left[:i+1]+right[j:]\n",
    "        result = mergecollision(asteroids)\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        s,p = [],0\n",
    "        while p < len(asteroids):\n",
    "            if not s or s[-1]<0 or asteroids[p] > 0:\n",
    "                s.append(asteroids[p])\n",
    "            elif s[-1] <= -asteroids[p]:\n",
    "                if s.pop() < -asteroids[p]:\n",
    "                    continue\n",
    "            p+=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        s, p = [], 0\n",
    "        while p < len(asteroids):\n",
    "            if not s or s[-1] < 0 or asteroids[p] > 0:\n",
    "                s.append(asteroids[p])\n",
    "            elif s[-1] <= -asteroids[p]:\n",
    "                if s.pop() < -asteroids[p]:\n",
    "                    continue\n",
    "            p += 1\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for x in asteroids:\n",
    "            if not stack or x>0:\n",
    "                stack.append(x)\n",
    "            else: #x<0\n",
    "                while 1:\n",
    "                    top = stack[-1] if stack else None\n",
    "                    if top is None:\n",
    "                        stack.append(x)\n",
    "                        break \n",
    "                    elif top < 0:\n",
    "                        stack.append(x)\n",
    "                        break\n",
    "                    elif abs(top) > abs(x):\n",
    "                        break\n",
    "                    elif abs(top) == abs(x):\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                    elif abs(top) < abs(x):\n",
    "                        stack.pop()\n",
    "                        continue\n",
    "                    else:\n",
    "                        break\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        s, p = [], 0\n",
    "        while p < len(asteroids):\n",
    "            if not s or s[-1] < 0 or asteroids[p] > 0:\n",
    "                s.append(asteroids[p])\n",
    "            elif s[-1] <= -asteroids[p]:\n",
    "                if s.pop() < -asteroids[p]:\n",
    "                    continue\n",
    "            p += 1\n",
    "        return s\n",
    "\n",
    "# 作者：清风Python\n",
    "# 链接：https://leetcode.cn/problems/XagZNi/description/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isInsertAsteroid(stack, asteroid):\n",
    "    pass\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for i in range(len(asteroids)):\n",
    "            if asteroids[i] > 0:\n",
    "                stack.append(asteroids[i])\n",
    "            else:\n",
    "                if not stack:\n",
    "                    stack.append(asteroids[i])\n",
    "                    continue\n",
    "                if stack[-1] < 0:\n",
    "                    stack.append(asteroids[i])\n",
    "                    continue\n",
    "                else:                    \n",
    "                    while stack and (stack[-1] > 0) and (abs(stack[-1]) < abs(asteroids[i])) :\n",
    "                        stack.pop()\n",
    "                    if not stack:\n",
    "                        stack.append(asteroids[i])\n",
    "                        continue\n",
    "                    if (stack[-1] > 0) and (abs(stack[-1]) == abs(asteroids[i])):\n",
    "                        stack.pop()\n",
    "                        continue\n",
    "                    if (stack[-1] > 0) and (abs(stack[-1]) > abs(asteroids[i])):\n",
    "                        continue    \n",
    "                    stack.append(asteroids[i])        \n",
    "        return stack                \n",
    "                            \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        ans = [-1 for i in range(len(asteroids))]\n",
    "        wait = []\n",
    "        for i, v in enumerate(asteroids):\n",
    "            if v < 0:\n",
    "                live = True\n",
    "                while len(wait):\n",
    "                    tmp = wait[-1][1]\n",
    "                    if tmp > abs(v):\n",
    "                        live = False\n",
    "                        break\n",
    "                    elif tmp == abs(v):\n",
    "                        wait.pop()\n",
    "                        live = False\n",
    "                        break\n",
    "                    else:\n",
    "                        wait.pop()\n",
    "                if live:\n",
    "                    ans[i] = 1\n",
    "            else:\n",
    "                wait.append((i, v))\n",
    "        \n",
    "        for i in wait:\n",
    "            ans[i[0]] = 1\n",
    "\n",
    "        out = []\n",
    "        for i in range(len(asteroids)):\n",
    "            if ans[i] == 1:\n",
    "                out.append(asteroids[i])\n",
    "        return out\n",
    "\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for a in asteroids:\n",
    "            if a > 0:\n",
    "                res.append(a)\n",
    "            else:\n",
    "                broken = False\n",
    "                while res and res[-1] > 0:\n",
    "                    tmp = abs(a)\n",
    "                    if tmp == res[-1]:\n",
    "                        broken = True\n",
    "                        res.pop()\n",
    "                        break\n",
    "                    elif tmp < res[-1]:\n",
    "                        broken = True\n",
    "                        break\n",
    "                    else:\n",
    "                        res.pop()\n",
    "                if not broken:\n",
    "                    res.append(a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for a in asteroids:\n",
    "            if a > 0:\n",
    "                st.append(a)\n",
    "                continue\n",
    "            flag = 1\n",
    "            while st and st[-1] > 0 and abs(a) >= st[-1]:\n",
    "                if abs(a) == st.pop():\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag and (not st or st[-1] < 0):\n",
    "                st.append(a)\n",
    "        return st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def asteroidCollision(self, asteroids):\n",
    "#         s, p = [], 0\n",
    "#         while p < len(asteroids):\n",
    "#             if not s or s[-1] < 0 or asteroids[p] > 0:\n",
    "#                 s.append(asteroids[p])\n",
    "#             elif s[-1] <= -asteroids[p]:\n",
    "#                 if s.pop() < -asteroids[p]:\n",
    "#                     continue\n",
    "#             p += 1\n",
    "#         return s\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        s,p=[],0\n",
    "        while p<len(asteroids):\n",
    "            if not s or s[-1]<0 or asteroids[p]>0:\n",
    "                s.append(asteroids[p])\n",
    "            elif s[-1]<=-asteroids[p]:\n",
    "                if s.pop()<-asteroids[p]:\n",
    "                    continue\n",
    "            p+=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for a in asteroids:\n",
    "            if a > 0:\n",
    "                st.append(a)\n",
    "                continue\n",
    "            flag = 1\n",
    "            while st and st[-1] > 0 and abs(a) >= st[-1]:\n",
    "                if abs(a) == st.pop():\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if not st and flag:\n",
    "                st.append(a)\n",
    "            elif st and st[-1] < 0 and flag:\n",
    "                st.append(a)\n",
    "        return st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for aster in asteroids:\n",
    "            alive = True\n",
    "            while alive and aster < 0 and st and st[-1] > 0:\n",
    "                alive = st[-1] < -aster\n",
    "                if st[-1] <= -aster:\n",
    "                    st.pop()\n",
    "            if alive:\n",
    "                st.append(aster)\n",
    "        return st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for aster in asteroids:\n",
    "            alive = True\n",
    "            while alive and aster < 0 and st and st[-1] > 0:\n",
    "                alive = st[-1] < -aster\n",
    "                if st[-1] <= -aster:\n",
    "                    st.pop()\n",
    "            if alive:\n",
    "                st.append(aster)\n",
    "        return st\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        # 只有左栈和右栈同时不为空时才会发生相撞\n",
    "        left_stack = []\n",
    "        right_stack = []\n",
    "        # no_use表示左侧的行星往左跑, 永远不会撞到其他行星\n",
    "        no_use = []\n",
    "        for i in asteroids:\n",
    "            if i < 0:\n",
    "                if len(left_stack) > 0:\n",
    "                    right_stack.append(i)\n",
    "                else:\n",
    "                    no_use.append(i)\n",
    "            elif i > 0:\n",
    "                left_stack.append(i)\n",
    "            # print('---1---', no_use, left_stack, right_stack)\n",
    "            while left_stack and right_stack:\n",
    "                num1 = left_stack.pop()\n",
    "                num2 = right_stack.pop(0)\n",
    "                if abs(num1) > abs(num2):\n",
    "                    left_stack.append(num1)\n",
    "                elif abs(num1) < abs(num2):\n",
    "                    if len(left_stack) > 0:\n",
    "                        right_stack.append(num2)\n",
    "                    else:\n",
    "                        no_use.append(num2)\n",
    "            # print('---2---', no_use, left_stack, right_stack)\n",
    "        return no_use + left_stack + right_stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        for a in asteroids:\n",
    "            alive = True\n",
    "            while alive and a < 0 and s and s[-1] > 0:\n",
    "                alive = -a > s[-1]\n",
    "                if -a >= s[-1]:\n",
    "                    s.pop()\n",
    "            if alive:\n",
    "                s.append(a)\n",
    "        return s\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        s, p = [], 0\n",
    "        while p < len(asteroids):\n",
    "            if not s or s[-1] < 0 or asteroids[p] > 0:\n",
    "                s.append(asteroids[p])\n",
    "            elif s[-1] <= -asteroids[p]:\n",
    "                if s.pop() < -asteroids[p]:\n",
    "                    continue\n",
    "            p += 1\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for aster in asteroids:\n",
    "            alive = True\n",
    "            while alive and aster < 0 and st and st[-1] > 0:\n",
    "                alive = st[-1] < -aster\n",
    "                if st[-1] <= -aster:\n",
    "                    st.pop()\n",
    "            if alive:\n",
    "                st.append(aster)\n",
    "        return st\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for x in asteroids:\n",
    "            if not stack or x>0:\n",
    "                stack.append(x)\n",
    "            else: #x<0\n",
    "                while 1:\n",
    "                    top = stack[-1] if stack else None\n",
    "                    if top is None:\n",
    "                        stack.append(x)\n",
    "                        break \n",
    "                    elif top < 0:\n",
    "                        stack.append(x)\n",
    "                        break\n",
    "                    elif abs(top) > abs(x):\n",
    "                        break\n",
    "                    elif abs(top) == abs(x):\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                    elif abs(top) < abs(x):\n",
    "                        stack.pop()\n",
    "                        continue\n",
    "                  \n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        # 行星列表小于等于1，直接返回\n",
    "        if len(asteroids)<=1:\n",
    "            return asteroids\n",
    "        \n",
    "        # 分治+递归\n",
    "        def mergecollision(seq):\n",
    "            if len(seq) <= 1:\n",
    "                return seq\n",
    "            mid = len(seq) // 2 \n",
    "            left = mergecollision(seq[:mid])\n",
    "            # print(\"left\",left)\n",
    "            right = mergecollision(seq[mid:])\n",
    "            # print(\"right\",right)\n",
    "            return merge(left, right)\n",
    "\n",
    "        # 合并\n",
    "        def merge(left, right):\n",
    "            # 如果两个列表有一个为空，直接合并返回\n",
    "            if (len(left)==0)|(len(right)==0):\n",
    "                return left+right\n",
    "            # 碰撞过程，从中间开始碰撞。 两边的都是碰撞过的不会内部碰撞\n",
    "            i = len(left)-1  # \n",
    "            j = 0\n",
    "            while i >=0  and j < len(right):\n",
    "                if (left[i] < 0) & (right[j]>0):  # 移动方向相反不碰撞\n",
    "                    break\n",
    "                elif ((left[i]>0)&(right[j]>0))|((left[i]<0)&(right[j]<0)): # 方向相同不碰撞\n",
    "                    break\n",
    "                elif left[i] < -right[j]: # 左边绝对值小\n",
    "                    i -= 1\n",
    "                elif left[i] > -right[j]:  # 左边绝对值大\n",
    "                    j += 1\n",
    "                else:  # 两边相等，一起爆炸\n",
    "                    i -= 1\n",
    "                    j += 1\n",
    "            return left[:i+1]+right[j:]\n",
    "        result = mergecollision(asteroids)\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for i in asteroids:\n",
    "            if st and st[-1]>0 and i<0:\n",
    "                while st and st[-1]>0 and st[-1]<abs(i):st.pop()\n",
    "                if not st:\n",
    "                    st.append(i)\n",
    "                    continue\n",
    "                if st[-1]>abs(i):continue\n",
    "                if st[-1]==abs(i):\n",
    "                    st.pop()\n",
    "                    continue\n",
    "            st.append(i)\n",
    "        return st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        q = []\n",
    "        for a in asteroids:\n",
    "            if a > 0:\n",
    "                q.append(a)\n",
    "            else:\n",
    "                breaked = False\n",
    "                while q and q[-1] > 0:\n",
    "                    cur = q.pop()\n",
    "                    if cur == -a:\n",
    "                        breaked = True\n",
    "                        break\n",
    "                    elif cur > -a:\n",
    "                        q.append(cur)\n",
    "                        breaked = True\n",
    "                        break\n",
    "                if not breaked:\n",
    "                    q.append(a)\n",
    "        return q\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for i in asteroids:\n",
    "            if i < 0 and len(stack) > 0:\n",
    "                if stack[-1] < 0:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while i < 0 and len(stack) > 0 and stack[-1] > 0:\n",
    "                        j = stack.pop()\n",
    "                        print(j)\n",
    "                        if abs(i) > abs(j):\n",
    "                            if (len(stack) == 0 or stack[-1] < 0):\n",
    "                                stack.append(i)\n",
    "                        elif abs(i) < abs(j):\n",
    "                            stack.append(j)\n",
    "                            i = 0\n",
    "                        else:\n",
    "                            i = 0\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for aster in asteroids:\n",
    "            alive = True\n",
    "            while alive and aster < 0 and st and st[-1] > 0:\n",
    "                alive = st[-1] < -aster\n",
    "                if st[-1] <= -aster:\n",
    "                    st.pop()\n",
    "            if alive:\n",
    "                st.append(aster)\n",
    "        return st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums) \n",
    "        p1 = 1 \n",
    "        lt = [nums[0]] \n",
    "        while p1 < N: \n",
    "            if len(lt)>0 and lt[-1] > 0 and nums[p1] < 0:     # 会相撞\n",
    "                s = nums[p1] + lt[-1]\n",
    "                if s == 0:              # 大小相同\n",
    "                    lt.pop() \n",
    "                    p1 += 1\n",
    "                elif s < 0:             # 右边向左的星球大\n",
    "                    lt.pop() \n",
    "                else: \n",
    "                    p1 += 1 \n",
    "            else: \n",
    "                lt.append(nums[p1])\n",
    "                p1 += 1 \n",
    "        return lt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Stack(object):\n",
    "    def __init__(self):\n",
    "        self.tmp = list()\n",
    "\n",
    "    def push(self, val):\n",
    "        self.tmp.append(val)\n",
    "\n",
    "    def pop(self):\n",
    "        if self.tmp:\n",
    "            return self.tmp.pop(-1)\n",
    "\n",
    "    def empty(self):\n",
    "        if self.tmp:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "    def peek(self):\n",
    "        if self.tmp:\n",
    "            return self.tmp[-1]\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.tmp)\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = Stack()\n",
    "        for asteroid in asteroids:\n",
    "            while 1:\n",
    "                if stack.empty():\n",
    "                    stack.push(asteroid)\n",
    "                    break\n",
    "                if stack.peek() > 0 > asteroid:\n",
    "                    if abs(stack.peek()) > abs(asteroid):\n",
    "                        break\n",
    "                    elif abs(stack.peek()) == abs(asteroid):\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                        # stack.push(asteroid)\n",
    "                        # break\n",
    "\n",
    "                else:\n",
    "                    stack.push(asteroid)\n",
    "                    break\n",
    "\n",
    "        return stack.tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "\n",
    "        for asteroid in asteroids:\n",
    "            alive = True\n",
    "            while alive and asteroid < 0 and st and st[-1] > 0:\n",
    "                alive = st[-1] < -asteroid\n",
    "                if st[-1] <= -asteroid:\n",
    "                    st.pop()\n",
    "            if alive:\n",
    "                st.append(asteroid)\n",
    "\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for i in range(len(asteroids)):\n",
    "\n",
    "            is_disminished = False\n",
    "            while stack:\n",
    "                if stack[-1] * asteroids[i] > 0:\n",
    "                    stack.append(asteroids[i])\n",
    "                    break\n",
    "                else:\n",
    "                    if stack[-1] < 0 and asteroids[i] > 0:\n",
    "                        stack.append(asteroids[i])\n",
    "                        break\n",
    "                    cur = stack.pop(-1)\n",
    "                    if abs(cur) < abs(asteroids[i]):\n",
    "                        continue\n",
    "                    elif abs(cur) == abs(asteroids[i]):\n",
    "                        is_disminished = True\n",
    "                        break\n",
    "                    else:\n",
    "                        stack.append(cur)\n",
    "                        break\n",
    "            \n",
    "            if not stack and not is_disminished:\n",
    "                stack.append(asteroids[i])\n",
    "        return stack\n",
    "        \n",
    "            \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for aster in asteroids:\n",
    "            alive = True\n",
    "            while alive and aster < 0 and st and st[-1] > 0:\n",
    "                alive = st[-1] < -aster\n",
    "                if st[-1] <= -aster:\n",
    "                    st.pop()\n",
    "            if alive:\n",
    "                st.append(aster)\n",
    "        return st\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "\n",
    "        stack = []\n",
    "        for asteroid in asteroids:\n",
    "            alive = True \n",
    "            while alive and stack and stack[-1] > 0 and asteroid < 0:\n",
    "                if abs(asteroid) <= abs(stack[-1]):\n",
    "                    alive = False \n",
    "                if abs(asteroid) >= abs(stack[-1]):\n",
    "                    stack.pop()\n",
    "            if alive:\n",
    "                stack.append(asteroid)\n",
    "\n",
    "                \n",
    "        return stack "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        left=[]\n",
    "        right=[]\n",
    "        for aste in asteroids:\n",
    "            if aste>0:\n",
    "                right.append(aste)\n",
    "            while right and right[-1]<-aste:\n",
    "                right.pop()\n",
    "            if right and right[-1]==-aste:\n",
    "                right.pop()\n",
    "            elif not right:\n",
    "                left.append(aste)\n",
    "        return left+right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for a in asteroids:\n",
    "            while stack and 0 < stack[-1] < -1*a:#栈顶弹出，然后继续循环\n",
    "                stack.pop()\n",
    "            if not stack or stack[-1] < 0 or a > 0: #不碰撞\n",
    "                stack.append(a)\n",
    "            elif stack[-1] == -1*a:#同时装\n",
    "                stack.pop()\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "\n",
    "        for ast in asteroids:\n",
    "            cur_ast = ast\n",
    "            while stack and stack[-1] > 0 and cur_ast < 0:\n",
    "                last_ast = stack.pop()\n",
    "\n",
    "                if last_ast > abs(cur_ast):\n",
    "                    cur_ast = last_ast\n",
    "                elif last_ast == abs(cur_ast):\n",
    "                    cur_ast = 0\n",
    "\n",
    "            if cur_ast != 0:\n",
    "                stack.append(cur_ast)\n",
    "        \n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack,p = [],0\n",
    "        while p<len(asteroids):\n",
    "            if not stack or stack[-1]<0 or asteroids[p]>0:\n",
    "                stack.append(asteroids[p])\n",
    "            elif stack[-1] <= -asteroids[p]:\n",
    "                if stack.pop()<-asteroids[p]:\n",
    "                    continue\n",
    "            p+=1\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for a in asteroids:\n",
    "            if not stack or stack[-1] < 0 or a > 0:\n",
    "                stack.append(a)\n",
    "            else:\n",
    "                while stack and stack[-1] > 0:\n",
    "                    if stack[-1] + a == 0:\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                    elif stack[-1] + a > 0:\n",
    "                        break\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                        if not stack or stack[-1] < 0:\n",
    "                            stack.append(a)\n",
    "                            break\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, a: List[int]) -> List[int]:\n",
    "        top=-1;st=[0]*len(a)\n",
    "        i=0\n",
    "        while i<len(a):\n",
    "            flag=True\n",
    "            while top!=-1 and flag and a[i]<0 and st[top]>0:\n",
    "                if st[top]>=-a[i]:\n",
    "                    flag=False\n",
    "                if st[top]<=-a[i]:\n",
    "                    top-=1\n",
    "            if flag:\n",
    "                top+=1;st[top]=a[i]\n",
    "            i+=1\n",
    "        return st[:top+1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
